package site.wanjiahao.sort.uncompare;

import site.wanjiahao.sort.Sort;

// 计数优化
public class RadixSort3 extends Sort<Integer> {


    @Override
    protected void sort() {
        int max = array[0];
        for (int e : array) {
            if (e > max) {
                max = e;
            }
        }
        // 创建一个二维数组，存放元素
        int[][] buckets = new int[10][array.length];
        int[] bucketsSize = new int[10];
        for (int divider = 1; divider <= max; divider *= 10) {
            // 分别对每一位进行排序
            for (Integer integer : array) {
                int num = integer / divider % 10;
                // 找到桶最后一个元素存放
                buckets[num][bucketsSize[num]++] = integer;
            }

            // 按顺序，存入原来的数组
            int n = 0;
            for (int j = 0; j < 10; j++) {
                for (int i = 0; i < bucketsSize[j]; i++) {
                    array[n++] = buckets[j][i];
                }
                bucketsSize[j] = 0;
            }
        }
    }

}
